This invention relates generally to systems for processing database queries, and more specifically to systems for processing database queries by creating a distributed locality, cost-based execution plan.
Database management systems (DBMS) manage data records stored on storage devices. The data is often distributed across multiple storage devices organized by a server and accessible over a network. A client presents a query, the DBMS processes the query and returns results to the client. These systems suffer from performance problems related to processor speed, memory speed, disk access time and network bandwidth.
Attempts to solve the performance problem of query processing in a distributed database environment can be generally characterized by three approaches: “fat pipe”, clustering and active disk.
The “fat pipe” solutions simply attempt to increase overall query processing performance by increasing the network bandwidth. No modification is made to the query processing itself, data and instructions just travel over a faster communications medium. Storage systems manufactured by EMC Corporation of Hopkinton, Mass. exemplify this approach.
Clustering of computers to perform database queries allows for parallel processing to occur. Parallel computer architectures generally fall into two categories: symmetric multiprocessing (SMP) and massively parallel processing (MPP). SMP systems contain multiple processors which share the same memory containing one copy of the computer application and data. SMP systems reduce transaction time by dividing computer operations into tasks which execute on assigned processors. MPP systems contain many processors, each with their own memory containing a copy of a portion or all of the computer application and/or data. Each processor can then work independently on its portion of the data to reduce overall transaction time. In database systems, data records can be striped across multiple disk drives connected to these clusters of computers. Each computer in a cluster can process parts of the database query on a group of data records that it has access to. Where “fat pipe” solutions attack the database query performance problem by increasing network bandwidth, clustering solutions attack the database query performance problem by increasing processing capacity. Oracle Corporation of Redwood Shores, Calif. provides an SMP clustering solution in its Oracle 8i database product.
A third approach to improving database query processing performance is “active disk” technology. Active disks combine computer processing with physically linked disk drives to provide parallel processing of database queries that also reduces the load on the communications network. This processing approach may be used to provide database management functionality on a processor closely linked to the database storage device. Conventional and proposed active disk systems only provide fixed functionality query processors and do not provide overlapping query processor functionality. Systems exemplifying this approach are described below.
A thesis by Eric Reidel entitled “Active Disks—Remote Execution for Network Attached Storage” (Technical Report CMU-CS-99-177, Pittsburgh, Pa., November 1999) describes disks with programmable processors. The thesis evaluates scan-based algorithms that allow for parallel processing of database queries. Reidel proposes a massively parallel processing (MPP) system using identical processors.
Another active disk system is described in a paper entitled “Active Disks: Programming Model, Algorithm and Evaluation” by Acharya (University of California Santa Barbara), Uysal (University of Maryland College Park) and Saltz (University of Maryland College Park) (Proceedings of the 8th International Conference on Architectural Support for Programming Languages and Operating Systems ASPLOS VIII, October 1998). The paper by Acharya et. al. describes a concept of moving processing closer to disks, but lacks a teaching of an overall database architecture outlining where and how all database operations are organized and optimally executed.
The 1999 doctoral dissertation by Kimberly Keeton of the University of California Berkeley, entitled “Computer Architecture Support for Database Applications” describes the concept of “intelligent disks” or “idisks” as an array of intelligent disk controllers. The idisks are user programmable processors and memory packaged on a disk storage device coupled to a high speed communications link. The idisks in the array can work together to provide parallel processing of database queries. Keeton only describes a single type of processor with non-overlapping functionality. Alternative future architectures are hinted at, but not enabled. Also at the University of California Berkeley research on introspective storage or “istore” has been done by David Patterson (http://istore.cs.berkeley.edu). Istore proposes the concept of intelligent disk “bricks” configured on a chassis having redundant components for “self-healing”. Each brick comprises a CPU, memory, redundant network interfaces and a disk drive. The istore architecture is similar to Keeton's idisk architecture and suffers from many of the same deficiencies.
Commercial attempts to provide improved speed for processing database queries include a system sold by Teradata, a division of NCR Corporation. Teradata provides classic MPP database query processing systems having two classes of fixed function processors. The first class of processors are Access Module Processors (AMP) which execute queries in parallel. The AMPs access data on directly attached disk drives. The second class of processors are InterFace Processors (IFP). The IFPs parse, optimize and direct execution of the database queries executed on the AMPs. IFPs and AMPs are connected using a redundant, tree-shaped interconnect. The AMP/IFP architecture provides only one type of execution processor without overlapping functionality capability and no multiple locale optimization or execution options. Teradata has evolved the hardware-based AMP/IFP architecture into a hardware/software architecture with nodes running software versions of the AMP and IFP processors, but the AMP and IFP processes still are restricted to the fixed functionality of the hardware-based architecture. The software-based architecture also does not provide multiple locale optimization or execution options.